package 剑指offer.堆栈队列;

import java.util.Stack;

/*
输入两个整数序列，
第一个序列表示栈的压入顺序，
请判断第二个序列是否可能为该栈的弹出顺序。
假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，
序列4,5,3,2,1是该压栈序列对应的一个弹出序列，
但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
 */
public class 第31题栈的压入弹出序列 {

    /**
     * 既然已知入栈和出栈序列，则可以模拟一次入栈，每次入栈时都检查当前入栈后再出栈的元素是否等于出栈序列的第一个值
     * 若是的，则出栈。且出栈序列也出栈。
     * 这样一直轮询下去，直到遍历完入栈序列，
     * 若此时出栈序列不为空，表示stack与pop不匹配，则返回 false
     *
     * @param pushA 入栈序列
     * @param popA 出栈序列
     * @return
     */
    public boolean IsPopOrder(int[] pushA, int[] popA) {
        if (pushA == null || popA == null || pushA.length == 0 || popA.length == 0)
            return false;
        if (pushA.length != popA.length)
            return false;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0, j = 0; i < pushA.length; ) {
            // 入栈序列，开始入栈
            stack.push(pushA[i++]);
            // 如果此时栈的出栈序列等于 popA 的
            while (j < popA.length && stack.peek() == popA[j]) {
                // 那就检测下一个序列
                stack.pop();
                // j++ 应该放到这里面，一旦出现乱序的出栈序列（可能是正确的序列）
                // 需要保持当前的 j 的值不变，为了后面的for循环可以把指针指向与j相同的值
                j++;
            }
        }
        // 最后比较完了，若是pushA的序列，则stack应该pop结束
        return stack.isEmpty();
    }
}
